package problem1020;

import java.util.LinkedList;
import java.util.Queue;

//1020.飞地的数量
//https://leetcode.cn/problems/number-of-enclaves/

class Solution {
    public int numEnclaves(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        boolean[][] st = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        for(int j = 0; j<m; j++) {
            if(grid[0][j] == 1) {
                queue.add(new int[]{0, j});
                st[0][j] = true;
            }
            if(grid[n-1][j] == 1) {
                queue.add(new int[]{n-1, j});
                st[n-1][j] = true;
            }
        }
        for(int i = 0; i<n; i++) {
            if(grid[i][0] == 1) {
                queue.add(new int[]{i, 0});
                st[i][0] = true;
            }
            if(grid[i][m-1] == 1) {
                queue.add(new int[]{i, m-1});
                st[i][m-1] = true;
            }
        }

        int[] xx = {1,-1,0,0};
        int[] yy = {0,0,1,-1};
        while(!queue.isEmpty()) {
            int[] t = queue.poll();
            int x = t[0], y = t[1];
            for(int i = 0; i<4; i++) {
                int dx = x + xx[i], dy = y + yy[i];
                if(dx >= 0 && dx < n && dy >= 0 && dy < m && grid[dx][dy] == 1 && !st[dx][dy]) {
                    queue.add(new int[]{dx, dy});
                    st[dx][dy] = true;
                }
            }
        }

        int ret = 0;
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(grid[i][j] == 1 && !st[i][j]) ret++;
            }
        }
        return ret;
    }
}